Modern telecommunication networks carry different types of traffic having different Quality of Service (QoS) requirements. QoS requirements can be defined using various parameters for a desired communication path. These parameters include bandwidth, delay, jitter and loss probability, among others. The ability to fulfill QoS requirements depends on the actual path selected in the network for carrying the traffic. Path selection therefore has to consider application dependent QoS requirements associated with the traffic. Without an efficient QoS routing algorithm to select the path that meets the specified QoS requirements, networks may fail to find a path and reject a request for a connection, even though there might be an appropriate path available to successfully establish the connection. In addition to the use of QoS requirements in path selection, the selection of a path with a minimum cost, which is also referred to as “administrative weight,” is desirable, for example, to minimize the overall load on the network of the new path.
FIG. 1 is a view of a modem telecommunications environment. In FIG. 1, homes, businesses, schools, government institutions, hospitals, etc., all connect into the telecommunications network, seeking to transfer data, text, graphic images (including scanned images or computer generated graphics), audio (including voice, music, computer generated sounds and other natural sounds (animals, the ocean, a rockslide, etc.)), video, and combinations thereof. Coaxial cable, fiber-optic cable, fiber & coax, twisted copper lines, RF (including line-of-sight (LOS)) transmissions, and satellite transmission systems), and other means of connectivity link these institutions to each other.
FIG. 2 illustrates various nodes, and links between these nodes in an exemplary communication system. The communication system includes nodes S, A, B, C, D, X, Y, Z, and T, and the various links between these nodes. Nodes, in practical applications, are telephone switching stations, routers, receivers and transmitters, or any electronic system capable of receiving a signal in, and transmitting a signal out. Links are the means of connecting the practical electrical nodes; LOS RF transmissions, fiber-optic cables, etc., as discussed above.
A link represents the physical connection between two nodes, with no other node between the two nodes. A path is a set of individual links that moves a signal from its origin, S, to its destination, T (otherwise shown as “S-T”). For example, path p (S-A-Y-T), path q (S-B-Z-T) and path r (S-C-X-T) are composed of different sets of links, yet still represent the path S-T. Each link and node has specifications which describe the ability to pass data through the node or link, and what effect there might be upon the data. For example, there are delays (e.g., queuing and propagation delays), costs (e.g., hop count, monetary cost, or some measure of a link's capacity), and data error rates associated with each node and link. Thus, the goal is to create a set of nodes and links that meets or exceeds the QoS requirements for that path.
As an example of a typical communications network configuration, suppose, in FIG. 2, node S is an individual's home, and a call is being placed across the continental United States. The telephone call emanates from the residential home (node S) as twisted copper wire (link S-B), then is transmitted across the country (from node B) via a satellite transmission system (link B-Y). At the receiving end (node Y), the call is converted back from RF to twisted pair (link Y-T), which is the medium that enters the recipient's home or place of business (node T). It will be recognized and appreciated by those skilled in the art, that a separate line which emanates from S might be a CATV coax line (link S-A), or fiber optic line (link S-C). Depending on the application, the individual at node S could have a choice of which link to route a signal. Then, a QoS requirement might be established which is path dependent.
It will be recognized that although the number of variations of links and nodes which can establish a path are potentially unlimited, in practice, the goal is to minimize signal degradation and maximize correct transmission of data. Thus, the need to optimize links between nodes and ultimately, the path S-T.
The parameters that are used to satisfy QoS requirements can be either cumulative or non-cumulative. Non-cumulative parameters are those that do not add together or “accumulate” by the addition of subsequent nodes and links. However, it might be the case that the quality of the overall path is limited by the link or node with the worst non-cumulative parameters. Examples of non-cumulative parameters are bandwidth and access rights. The non-cumulative parameters can be easily handled by simply ignoring the links that do not fulfill the QoS requirements during the path selection process. Cumulative parameters can be either additive (e.g., delay, jitter and administrative weight) or multiplicative (e.g., loss probability). The simultaneous presence of more than one cumulative parameter is difficult to handle.
The problem of finding a path which fulfills two simultaneous cumulative parameters or finding a minimum cost path which satisfies only one cumulative parameter is designated “NP-Hard.” “NP” means “Non-deterministic Polynomial.” See, for example, the book “Combinatorial Optimization” by W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver (John Wiley & Sons, 1998) for more details, the contents of which are incorporated herein by reference.
There are two classes of methods used to solve NP-Hard problems. Methods of the first class, referred to as “Optimal-Solution” methods, guarantee an optimal solution, but are complex and relatively slow. The second class is referred to as “Approximation” methods, and use a heuristic (trial and error) or approximation technique to solve the NP-Hard problem. Approximation methods usually run fast, but they do not result in the optimal solution. They do, however, provide a solution that is near-optimal. Approximation methods usually do not guarantee the quality of their results and hence they need to be thoroughly tested. Additionally, the solution for both classes of methods cannot be expressed as a polynomial.
For both classes of methods, it is highly desirable to increase the theoretical guarantees on the running time of the method and the quality of the result of the method. With respect to Optimal Solution methods, one example is a “Breadth-First Search” method. This method determines the delay of all initial links, and then, building on that link, considers subsequent links, again, using only the one with the minimal delay. For example, referring again to FIG. 2, to establish a path from node S to node T, the Breadth-First Search method would first determine the delay in links S-A, S-B and S-C. The method would then select the link with the least delay, e.g. S-C, and then determine which links out of C-B, C-X, C-Y and C-Z have the smallest delay. The delay for each link is determined and is added to the previous links, to maintain a running total. This continues until either the destination is reached, the delay constraint is reached, or there is no possibility to improve the path. However, the “Breadth-First Search” method is guaranteed to be fast, but can find a minimal path for only one cost (delay in this example). The Dijkstra algorithm is an example of a sophisticated Breadth-First search method.
There are several well known methods of the Approximation class of methods. One example is “Fallback Routing” which tries to find an appropriate path which meets all the QoS requirements. It tries one path after another, until a suitable path has been found, or no path is found that satisfies all the QoS requirements. This method is very simple, fast and always gives an appropriate solution if it exists. There is no guarantee, though, of finding the optimal path and no guarantee of the quality of the path found.
Both classes of well known methods, Approximation and Optimal-Solution, have significant drawbacks. Optimal-Solution methods provide an optimal solution, but are complex to use and relatively slow. Approximation methods run much quicker, but provide medium quality results and some types do provide a guarantee of the quality of the result. However, the better the guarantee of result, the slower the Approximation method runs. Additionally, it has been shown that for NP-Hard problems, no algorithm exists that determines a solution, the running time of which, can be expressed in polynomial form.
Thus, there has been demonstrated a genuine need for a method which is simple and easy to use, runs relatively quickly, and presents high quality optimal solutions for the problem of selecting a path in a telecommunications network that meets specified QoS requirements. The method of the present invention fulfills the long-felt need of choosing effective paths in modern telecommunication networks.